class Solution {
public:
    Node* copyRandomList(Node* head) {
        //这道题目的解法为我将我构造的新链表的节点首先构造在原链表每一个节点的后面也就是
        //如果原链表为 1 2 3 那么我复制后链表结构就变成了 1 1 2 2 3 3其中后面多余的那个数字
        //就是我新复制的节点，但是在复制的时候我不对random指针进行赋值，然后我去遍历这个新的链表
        //如果遇到的这个节点的random不为空代表这是原节点，那么我就需要给我的复制节点的random进行赋值了
        //我的复制节点就是cur->next而我的这个复制节点的random应该指向的值应该是cur->random->next
        //经过这样的复制，我的复制链表的random指针也完成了拷贝，如果原链表derandow就是nullptr，
        //那么我的复制节点也不需要进行任何的处理
        //最后就是将我的复制链表从原链表中分离出来,这样这道题目就完成了
        //第一步去进行复制
        //处理特殊情况
        if(!head)
        {
            return head;//head为空
        }
        Node* cur = head;
        while(cur)
        {
            Node* newnode = new Node(cur->val);
            newnode->random = nullptr;
            newnode->next = cur->next;
            cur->next = newnode;
            cur = newnode->next;//去复制下一个节点
        }
        //然后是为我的复制节点拷贝random指针
        cur = head;
        while(cur)
        {
            if(cur->random)
            {
                cur->next->random = cur->random->next;
            }//cur的复制节点的random指针指向的就是cur->random指针指向节点的复制节点
            //random节点为空则不进行处理
            cur = cur->next->next;
        }
        //最后就是将我的链表和原来的链表进行分离了
        cur = head;
        Node* newhead = head->next;
        while(cur)
        {
            Node* tmp = cur->next;
            cur->next = tmp->next;//让原链表的next指向原来的下一个节点
            if(tmp->next)
            tmp->next = cur->next->next;//让我的链表指向我应该指向的那个节点
            cur = cur->next;
        }
        return newhead;
    } 
};